Many modern electronic devices, e.g. embedded devices, are controlled by software stored in flash memory. Flash memory is a type of memory that is frequently used in electronic devices, because it allows multiple rewrites. However, the write operations are limited to relatively large individual memory sectors, so-called erase blocks, at a time.
Previous embedded systems have frequently utilised so-called NOR flash memory and execution-in-place mechanisms where the software stored in the flash memory is executed directly from the flash memory. More recently, so-called NAND memory is increasingly used in embedded systems due to its relatively lower price for large storage capacities. However, due to its construction principles, NAND memory is generally not suitable for providing execution-in-place.
Embedded systems may use a combination of NOR and NAND memories, where a smaller NOR memory is used as software read-only-memory (ROM) and a larger NAND memory is partitioned with a file system for use as a random access storage area. However, the need for both NOR and NAND memories in such systems partly consumes the price advantage of NAND memory.
In other systems, the NAND is used both for software and constant data storage as well as random access storage. To this end, when executing software from NAND memories, virtual memory strategies are used, in which memory contents are first paged or copied from the NAND memory into memory-mapped random access memory (RAM) and executed there. Hence, in such systems, the NAND memory operates as a secondary medium/storage device, while the memory-mapped RAM operates as a primary memory.
Virtual memory or virtual memory addressing is a memory management technique, used by operating systems of computers and other processing devices, wherein non-contiguous memory is presented to a software/process as contiguous memory. This contiguous memory is referred to as the virtual address space.
Virtual memory is frequently implemented using paging. In paging, a range of consecutive addresses in a virtual address space (the range of addresses used by the processor) is mapped to a corresponding range of physical addresses of the memory. The memory referenced by such a range is called a page. The page size is typically in the range of 512 to 8192 bytes with a few e.g. 4 kbytes currently being a very common choice, though page sizes of 4 megabytes or larger may be used for special purposes.
The translation from virtual to physical addresses is typically implemented by a so-called memory management unit (MMU) that may be provided as a module of the central processing unit (CPU), or as an auxiliary, closely coupled chip. Memory management units thus are a class of computer hardware components responsible for handling memory accesses requested by the CPU. Apart from the translation of virtual addresses to physical addresses (i.e., virtual memory management), the MMU may perform further functions such as memory protection, cache control, bus arbitration, etc.
Demand paging is a particularly useful method of implementing virtual memory. In demand paging, the operating system copies a page from secondary memory (e.g. flash memory) into its primary memory (e.g. RAM), if an attempt is made to access it (e.g. if a page fault occurs).
In embedded systems it is generally desirable to reduce the storage requirements or to increase the storage capacity without increasing the amount of memory installed in the system, so as to keep production costs low.
The implementation of an embedded system that utilizes demand paging or other virtual memory techniques for executing code or reading constant data from virtual read-only memory has opened the possibility for compressing the code and constant data in the storage medium. The code and constant data is then to be decompressed when it is loaded into RAM for execution or read access by the CPU.
U.S. Pat. No. 6,349,375 discloses an embedded system in which data is stored in a storage medium in a compressed format. In response to a request for data by the CPU, the virtual memory system first determines whether the requested data is present, in uncompressed form, in the portion of main memory that is accessible to the CPU. If the requested data is not present in the decompressed portion of main memory but rather in a compressed format in the storage medium, the data is transferred into the decompressed portion of main memory by a demand paging operation. During the demand paging operation, the data is decompressed.
U.S. Pat. No. 6,332,172 discloses a method for reducing the memory requirements in a low resource computer system. In this prior art method a compressed image is stored in flash memory and pages of compressed memory are paged in at run-time, where the page-in operation includes decompressing the corresponding page data.
In such prior art methods and systems, the data may typically be compressed in portions of the same size as the MMU page size or multiples thereof (e.g. 4, 8 or 16 . . . kB). The compressed data corresponding to the respective memory pages will generally have a size smaller than the page size. However, due to the nature of data compression, the compressed data corresponding to the virtual memory pages will typically be of varying size, since the achievable compression ratio typically varies from page to page.
Consequently, the translation of virtual addresses to physical offsets in a consecutive image of concatenated compressed pages is non-linear and in practice requires a translation table. Such a translation table either needs to be stored in the storage medium or reconstructed at system boot. Assuming the minimal requirement of one word of 4 bytes per MMU-page and a MMU page size of 4 kB, the translation table would have a cost of 1 kB/MB. This translation table could be kept statically in RAM during the complete execution of the program, thereby increasing the RAM usage of the system. Alternatively, the translation table may be kept in the storage medium, thus causing the translation to result in an additional indirection through the storage medium. The extra time for reading this indirection would add to the time required to read the compressed data for one page, thus reducing the efficiency of the system.
In some storage media, such as hard-disks, NAND and other types of flash memories, data is accessed in entities larger than 1 byte, e.g. as disk sectors of a hard disk or NAND blocks, typically 512 bytes through a few Kbytes. For the purpose of the present description the entities larger than 1 byte in which the data is stored and/or accessed will be referred to as memory sectors or simply sectors. Consequently, in such systems, the additional read operation for reading the translation table would involve reading at least one such sector, and considerably increase the effective time to read a compressed page.
U.S. Pat. No. 5,666,114 discloses a method for accessing variable length compressed symbol strings in an addressable memory. According to this prior art method a compressed symbol exceeding the size of a linear or primary address segment is divided into a primary segment and an overflow segment such that a pointer to the overflow segment is embedded in the primary segment. The total fixed size address space is managed dynamically by adjusting the size of the linear segments and using the overflow space adjustably with the linear space to maintain a constant sum.
Hence this prior art method requires the system to dynamically vary the relative size of the linear address extent of the storage space and of the segments stored therein as the source symbol probabilities vary over time. This resizing involves a periodical and opportunistic rewriting of the linear and overflow extents as a function of whether the overflow has been under or overutilizes as a percentage of its current size. Depending on the storage medium such rewriting may require a considerable time and energy consumption. In particular for battery-driven devices and/or devices with limited computational resources such limitations may yield to a noticeable reduction of the performance of the device. Furthermore, a resizing of the primary segments further requires a change in the translation from the virtual to physical addresses. Furthermore, for certain types of storage media such as flash memory, the change of the size of the primary segments to sizes different from the block size of the storage medium may result in inefficient read and/or write operations.
Hence, it remains a problem to provide an improved method for storing compressed data in a storage medium.